#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <string>
#include <vector>
#pragma once

using namespace std;

//int main() {
//	string Sum("255DB2B8726A5F1AA53C381546BD7EE1779CC116EC2A09A2465033821D9468AF18FE0A7F5039B94DE507E7D0E379A0E56879C7F0A6D8D79AFA6B52848A7C30897E40F2977C41F8312AF13696D2D32FC5BA1D068BC3856A1E035A1CEB17A948F5");
//	vector<string> vs(16);
//	int count = 0;
//	for (int i = 0; i < 16; i++) {
//		string ch = "'";
//		vs[i].reserve(12);
//		vs[i] += ch;
//		int cnt = 12;
//		while (cnt--) {
//			vs[i] += Sum[count++];
//		}
//		vs[i] += ch;
//	}
//	for (auto& e : vs)
//		cout << e << endl;
//	return 0;
//}

#include <iostream>
#include <vector>

using namespace std;

//int main() {
//    int num, target;
//    cin >> num >> target;
//    vector<int> v(num + 1);
//    for (int i = 1; i <= num; i++)
//        cin >> v[i];
//    int retleft, retright;
//    retright = INT16_MAX;
//    retleft = 0;
//    long long sum = 0;
//    int left, right;
//    left = right = 1;
//    while (right <= num) {
//        if (sum >= target && right - left < retright - retleft) {
//            retright = right;
//            retleft = left;
//            sum -= v[left];
//            left++;
//            continue;
//        }
//        sum += v[right];
//        right++;
//    }
//    cout << retleft << " " << retright << endl;
//
//    return 0;
//}

#include <iostream>
//#include <vector>
//
//using namespace std;
//
//int main() {
//    int num, target;
//    cin >> num >> target;
//    vector<int> v(num + 1);
//    for (int i = 1; i <= num; i++)
//        cin >> v[i];
//    int retleft, retright;
//    retright = INT16_MAX;
//    retleft = 0;
//    long long sum = 0;
//    int left, right;
//    left = 1;
//    right = 1;
//    while (right <= num) {
//        sum += v[right];
//
//        while (sum >= target) {
//            if (right - left < retright - retleft) {
//                retright = right;
//                retleft = left;
//            }
//            sum -= v[left++];
//        }
//
//        right++;
//
//    }
//    cout << retleft << " " << retright << endl;
//
//    return 0;
//}

//#include <iostream>
//#include <vector>
//
//using namespace std;
//
//#include <queue>
//
//int main() {
//    int num, k;
//    cin >> num >> k;
//    vector<int> oddv;
//    priority_queue<int> evenq;
//    for (int i = 0; i < num; i++) {
//        int e;
//        cin >> e;
//        if (e % 2 == 0) evenq.push(e);
//        else oddv.push_back(e);
//    }
//    while (k-- && !evenq.empty()) {
//        int top = evenq.top();
//        evenq.pop();
//        top /= 2;
//        evenq.push(top);
//    }
//    long long sum = 0;
//    while (!evenq.empty()) {
//        sum += evenq.top();
//        evenq.pop();
//    }
//    while (!oddv.empty()) {
//        sum += oddv.back();
//        oddv.pop_back();
//    }
//    cout << sum << endl;
//    return 0;
//}

//#include <iostream>
//#include <vector>
//
//using namespace std;
//
//#include <queue>
//
//int main() {
//    int num, k;
//    cin >> num >> k;
//    vector<int> oddv;
//    priority_queue<int> evenq;
//    for (int i = 0; i < num; i++) {
//        int e;
//        cin >> e;
//        if (e % 2 == 0) evenq.push(e);
//        else oddv.push_back(e);
//    }
//    while (k-- && !evenq.empty()) {
//        int top = evenq.top();
//        evenq.pop();
//        top /= 2;
//        if (top % 2 == 0) evenq.push(top);
//        else oddv.push_back(top);
//    }
//    long long sum = 0;
//    while (!evenq.empty()) {
//        sum += evenq.top();
//        evenq.pop();
//    }
//    while (!oddv.empty()) {
//        sum += oddv.back();
//        oddv.pop_back();
//    }
//    cout << sum << endl;
//    return 0;
//}

#include <string>
#include <vector>
class Solution {
public:
    int m, n;
    bool vis[101][101] = { 0 };
    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    bool exist(vector<string>& board, string word) {
        // write code here
        m = board.size(), n = board[0].size();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == word[0])
                    if (dfs(board, i, j, word, 0)) return true;
            }
        }
        return false;
    }

    bool dfs(vector<string>& borad, int i, int j, string& word, int pos) {
        if (pos == word.size() - 1) return true;
        vis[i][j] = true;
        for (int k = 0; k < 4; k++) {
            int a = i + dx[k], b = j + dy[k];
            if (a >= 0 && a < m && b >= 0 && b < n && !vis[a][b] &&
                borad[a][b] == word[pos + 1]) {
                if (dfs(borad, a, b, word, pos + 1)) return true;

            }
        }
        vis[i][j] = false;
        return false;
    }

};

//empty()：检测容器是否为空
//size()：返回容器的元素个数
//front()：返回容器中第一个元素的引用
//push_back()：在容器尾部插入元素
//pop_back()：删除容器尾部元素